Several private information retrieval (PIR) schemes exist in the prior art. These (PIR) schemes allow a user to retrieve information (e.g., a document) from a database using a server without revealing the information they are retrieving. PIR is similar to 1-out-of-n oblivious transfer, where the user also does not get information about other information in the database. In the area of single-database symmetric PIR with preprocessing, a client making a query learns nothing more than the result of their query, while the server learns nothing about the contents of records returned for the query. The preprocessing stage in such a scheme is completed before engaging in the query stage.
PIR schemes generally require O(n) computation, with the exception of some systems with multiple servers. One prior art scheme achieves constant query time on a single server, but with O(n2) preprocessing per query. This scheme also makes use of a shuffling protocol to generate a shuffled hash table (as opposed to use in generating a shuffled tree structured index) and also requires use of a secure coprocessor. Other prior art techniques also make use of a shuffled hash table to achieve constant time queries with O(n) preprocessing, but require storing all data and performing the query at the client machine.
The PIR protocols used PIR schemes have employed various cryptosystems. A number of cryptosystems are well-known in the art and have a variety of properties.
Some cryptosystems have a commutative property. That is, the order in which encryption and decryption operations are applied does not affect the result of the operations. In a non-commutative encryption scheme, the order of the operations is relevant to the result. For example, consider a plaintext message m that has been encrypted with key k1 to yield the ciphertext c1=Ek1(m). Further, encrypt c1 with key k2 to yield the ciphertext c2=Ek2(Ek1(m)). In a noncommutative encryption scheme, decrypting with k1 before k2 yields garbage, while decrypting in the reverse order (k2, k1) yields the message m:
            D              k        2              ⁡          (                        D                      k            1                          ⁡                  (                                    E                              k                2                                      ⁡                          (                                                E                                      k                    1                                                  ⁡                                  (                  m                  )                                            )                                )                    )        =            ⊥                          ⁢                        D                      k            1                          ⁡                  (                                    D                              k                2                                      ⁡                          (                                                E                                      k                    2                                                  ⁡                                  (                                                            E                                              k                        1                                                              ⁡                                          (                      m                      )                                                        )                                            )                                )                      =    m  
In other words:Dk2(Dk1(c2))≠Dk1(Dk2(c2))
Commutative cryptosystems differ in that the following relation holds:Dk2(Dk1(c2))=Dk1(Dk2(c2))
Thus, the order of the operations does not affect the result. A commutative encryption scheme is useful in that it enables the entries in the database to be securely shuffled without revealing the location of any element to either party. With respect to some previous solutions, the commutative encryption scheme will serve as the secure coprocessor for our protocol.
A cryptosystem with a homomorphic property allows some subset of mathematical operations to be performed on encrypted messages. This is a desirable property, as it allows many simple functions to be computed securely and efficiently. In general, a homomorphic cryptosystem supports some binary operator ⋄, where the following property holds:E(x)·E(y)=E(x⋄y)
A cryptosystem is additively homomorphic when ⋄ is the addition operator, or multiplicatively homomorphic when ⋄ is the multiplication operator. For example, the Paillier cryptosystem is additively homomorphic, while the ElGamal and Massey-Omura are multiplicatively homomorphic. The Goldwasser-Micali cryptosystem supports the more complex binary operator exclusive-or. A multiplicatively homomorphic encryption scheme satisfies the property:E(x)·E(y)=E(x·y)
At least one prior art PIR scheme uses Paillier's additively homomorphic cryptosystem, which requires O(n) computation and database communication of O(kd), where k is the security parameter and dε+.
U.S. Pat. No. 6,167,392 describes a single-database PIR scheme based on the use of homomorphic encryption and the quadratic residuosity assumption. This PIR scheme requires a repeated interaction between the client and server until the desired record can be retrieved. Here, our invention achieves the goal with a constant number of rounds.
U.S. Pat. No. 5,855,018 describes another PIR scheme that requires the use of non-colluding replicated database servers.